• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:

    公开号:WO1987006081A1
    申请号:PCT/JP1987/000207
    申请日:1987-04-02
    公开日:1987-10-08
    发明作者:Hideo Suzuki；Masato Tajima
    申请人:Kabushiki Kaisha Toshiba；
    IPC主号:H03M13-00
    专利说明:
    [0001] 明 細 眷
    [0002] ゲ イ タ ビ復号器における ス メ モ リ 制御法
    [0003] [ 技術分野 ]
    [0004] こ の発明は ト レ ー スパ ッ ク に用いる ス メ モ リ O ア ク セ スを新 らた も の と したグ イ タ ビ復号器におけ る ス メ モ リ 制御法に関する。
    [0005] C 背景技術 ]
    [0006] ゥ，ィ タ ビ¾号器内部での復号動作のために、 ス メ モ リ には対象 とする符号 ト レ リ ス上の各状態に対し て生き残 ] ス と呼ばれる送信 ス と して最 も確か ら しい ス の侯補と な るべき も のが有限長で各々 i 本ず つ記憶されている。
    [0007] これ らの生き残 り スが実効的に 1 本に収束する と考え られる符号の拘束長の、 4 〜 5 倍程度過去の生 き残 り ス に共通 ¾ ビ ッ ト が復号データ と して出力さ れる 。
    [0008] この場合、 生き残 り スの記慷法と して具 ^的に は、 対応する記億回路に、 第 2 A図に示す よ 5 ¾ ト レ リ ス線図の举位セル構造に着目 し、 雜 ] 合 う 時刻間の 状態邊移情報 （ すなわち、 時刻 （ k + 1 ：) の状觼
    [0009] Xk+ 1がー時刻前の 2つの状態 Xk及び X のいずれか ら 遷移したと見るのが も っ と も ら しいかとい ゥ 1 ビ ッ ト の情報 ） を記憶してい く こ とが行なわれる。
    [0010] この よ ゥ ¾ 1 ビ ッ ト の状態遷移情報は、 ト レ リ ス コネク シ a ン デー タ tre l l i e connection Data と も呼 ばれ、 各復号ス テ ッ プ毎に各々 の状態に対し記億され てい く 。
    [0011] 従って、 この よ う な形で記憶された生き残 ] ス を基に復号を実行し ょ う とする と、 時刻 k における も つ と も ら しい状態 （ この状態に対して記慷されている 生き残 ス の ス の も っ と も ら しい度合がその他の いずれの状態に対して記憶されている生き残 ！） ス の ス の もっとも らしい度合よ り も大きい） を起点と し、 前 回の状態遷移情報を も と に逆向き にさかのぽ 、 最終 的に到達した状態： Sic-v ( V は生き残 ス長 ） に よ ί 復号データ を決める と い う、 いわゆる あ と も ど 5 動作
    [0012] ( ト レ ー スパ ッ ク、 trace backと呼ぶ ） を必要とする さ て こ の時刻 k か ら時刻 k 一 マ への ト レ ー ス パ ッ クは基本的に 1 復号ステ ツ ブ中に完了しなければ復号 データ を出力する こ とが出来 ¾い。 説明を明確にする ため、 生き残 パ ス記憶回路を第 3 図に示すよ う な ラ ン ダ 厶 ア ク セ ス メ モ リ に よ って実現する と考え、 縦軸 方向を ト レ リ ス の状態、 横轴方向を時間軸と して考え る こ とにする。 こ こで特に時刻 k ま での復号演算が終 了し、 新たに時刻 （ k + 1 ) の復号演算が開始された と考える。
    [0013] グイ タ ビ ア ル ゴ リ ズ ムに よ U演算部で決定された 各状觴遷移情報は次々 と メ モ リ に対し縦方向に書き込 ま れてい く が、， 一方復号のためにはこの香き込みが終 了する間に横方向に ト レ ー スパ ッ ク を実行し、 例えば 第 3 図の a¾では メ モ リ の左端ま で到達する こ とが要求 される。
    [0014] さて、 この場合の ト レ ー スパ ッ ク とは具体的に述 ベる と番地のア ク セ ス→状態遷移情報の読み出 し— ( 一時刻過去 ） のア ク セ ス番地の決定、 と い ウ サイ ク ル の繰 ！）返しを意味し、 従って通常は、 状態遷移情報 の メ モ リ への香き込みと ト レ ー スパ ッ クが交互に行な われる。
    [0015] しかし こ こで明 らかな よ う に、 ト レ リ ス の状態数 と生き残 り ス長が異な る と き （ 冽えば第 3 図の メ モ リ で言えば横方向に長い長方形の と き ） （ k + 1 ) 時 刻における全ての状態に対する状態遷移情報の香き込 みを終了した時点で ト レ ー スバ ッ クは左端ま で到達し ていない こ と に ¾ る。
    [0016] 又、 たとえ、 ト レ リ ス の状態数と生き残 り ス長 とが同 じである と して も、 冽えば、 複数の状糠に対す る状態遷移情報が一度に得られる よ ゥ な復号器の回路 構成では全ての状態に対する状態運移情報の香き 込み が終了した時点での、 ト レ ー スバ ッ クの実行は一度に 処理される複数の状態数であ って も、 一定長の ス分 だけしか遡れない。 即ち生き残 ス の途中 ¾までし か ト レ ー スパ ッ クができ ないこ とにな る。 従って従来は、 ト レ リ ス の状態数と生き 残 ί ス 長との間に適当な整合がと られていない こ都合 よ く メ モ リ を制御出来ないと い う 困難があ った。
    [0017] と ころが復号 IIへの入力デー タ の S/ に よ っては 生き残 り ス長を大き く と たいこ とがしばしば発生 する し、 演算部の回路構成に も 自 由度が要求される。 その他の イ タ ビ復号法に よ る ス メ モ リ のマネ ジ メ ン ト がある こ とは I EEE 「 TRANSACT I ON ON COMMUNI CAT I ONS 」 VOL , COM 2 9 , 9 , S EPTEMBER 1 9 8 1 に 記載されている こ とか ら知れるが確たる技術の改良の 記述はない。
    [0018] [ 発明の開示 ]
    [0019] 本発明は、 以上の問題点及び要求に鏟みるされた も ので、 記憶すべき生き残 D パ ス の ス長の変動、 あ るいは、 一変に得られる状態遷移情報の数の変動に対 し柔軟に対応出来る ト レースパ ッ ク構造を具備したダ ィ タ ビ復号器における ス メ モ リ 制御法を提供する こ と を目的とする。
    [0020] この発明は、 ダ イ タ ビ復号法において生き残 D ス の最終段ま での ト レースバ ッ クに複数の復号ステ ツ ブを要する と き、 上記 ト レ ー スパ ッ クに よ 費やした 復号ステ ッ プ数と同 じ数の復号データ を一度に出力す る ことを特徵とする。
    [0021] 生き残 り パ ス記憶回路上の ト レ ー スバ グ ク動作は 基本的にはー復号ス テ ツ プ毎に生き残 り ス の最終 ¾ ま で到達する こ と が原則であるが、 復号データ の得 ら れ方と い う 観点か ら考える と、 割合と して一復号ステ ッ プあた り 一個の復号データが得られれば良いとい う 認識に立ち、 生き残 り ス の最終段ま での ト レ ー スパ ッ ク に複数復号ス テ ッ プ要したとすれば、 こ の ト レ ー スバ ッ ク に よ り ただ一個の復号デー タ を出力するので な く 、 費やした復号ス テ ッ プ数と 同 じ数の復号データ を出力する よ う に した ものである 。
    [0022] すなわち、 復号器の演箅部て得られる状態遷移情 報 （ 一般には一度に複数個 ：） 'を生き残 り パ ス記憶回路 へ眷き込む毎に 1 段の ト レ ー ス バ ッ ク を実行し、 着目 している時刻における全状態に対する状態遷移情報の 香き込みを終了した時点で、 生き残 り ス の最終段ま での ト レ ー スパ ッ クが完了しないと き は、 更に続けて、 次の時刻に対する状態遷移情報の香き 込みと ト レ ー ス パ ッ クを継続し、 最終的に生き残 り ス の最終段ま で の ト レ ー スパ ッ クが完了した時点で、 この ト レ ー スパ ッ ク に费やされた復号ステ ツ プ数に相当する復号デ一 タをま と めて復号する よ う にした も のであ iる。
    [0023] 更に この発明のダ イ タ ビ復号器における パ ス メ モ リ 制御法は、 ス選択信号 （ 1 時刻聞の状態遷移愔報 ） を複数時刻間にわたって合成する こ と に よ 、 複数時 刻間にわたる状態遷移情報を合成し、 これを ス メ モ リ 回路へ記憶する こ と に よ U、 従来に比べて非常に少 ¾ い、 ス メ モ リ 回路へのア ク セ ス に よ り 生き残 り ス の最終段ま で ト レ ー ス パ ク し、 これに よ U 高速復 号動作を実現し ょ う とする も のである。 その着眼点を 要約すればパ ス選択信号は、 隣接時刻間、 従って一時 刻間の状態遷移愔報を表現してお り、 これを記慷した ス メ モ リ 回路では、 1 段毎の ト レ ー ス パ ッ ク の積み 重ねに よ jp 生き残 り スをさかのぼる しかない。
    [0024] と ころが複数時刻間のわたる状態遷移情報を扱 う よ う にすれば、 1 回の メ モ リ アク セスに よ り 複数段ヅ ヤ ン プしてバ ッ クする こ とができ、 従って少ない ス メ モ リ 回路へのアク セ ス に よ り 生き残 ス の最終段 ま でさかのぼる こ とがで き る。
    [0025] [ 図面の簡単 ¾説明 ]
    [0026] 第 1 図は、 この発明の一実施冽を説明するために 係わる グ イ タ ビ復号器のブ ロ ツ ク回路構成図 ；
    [0027] 第 2 Α図及び第 2 Β 図は、 符号 ト レ リ ス.線図の具 刿を示す図及びその単位セルの搆造列を示す図 ； 第 3 図は、 生き残 り ス記慷回路を ラ ン ダ ムァク セス メ モ リ に よ ！？ 実現する と き の メ モ リ 回路の模式図 第 4 図は、 符号化率 ½拘束長 k - 7 に対する復号 器を第 1 図の よ ゥ に構成したと き の対応する生き残 り ス記億回路の模式図 ；
    [0028] 第 5 A図及び第 5 B 図は、 この発明の一実施 ^の ト レ ー スバ ッ ク における異 ¾ る ス長の復号原理図 ； 第 6 図は、 この発明の他の実施 における ト レ ー ス パ グ ク の原理を説明する図 ；
    [0029] 第 7 図はこの発明の第 6 図の実施 ^における単位 セ ル構造を示す図 ：
    [0030] 第 8 図は、 この発明の第 6 図の実施 ^における復 号器を示すプ ロ ジ ク回路構成図 ；
    [0031] 第 9 図は、 2 個のバ ッ ク ト レ ーサに対応して生き 残 り ス記憶回路を 2 個の RAMに よ 実現した ^を示 す図 ；
    [0032] 第 1 0 図は、 複数の遷移情報を一度にパ ス メ モ リ に眷き込むために 2 個の ACS 回路を設けたブロ ッ ク回 路構成冽を示す図 ；
    [0033] 第 1 1 図は、 こ の発明の他の実施冽を説明するた めの復号手順を示すタ イ ム チ ャ ー ト を示す。
    [0034] C 実施の最炱の^態 ]
    [0035] ^下本発明の一実施洌を図面を参照して詳細に説 明する。
    [0036] —股性を失 う こ と な く 符号化率 ½拘束長 k - 7 の 符号を対象とする。 この場合、 ト レ リ ス上の状態数は 2k"1 - 2ά - 6 4 である。 必要とされる生き残 り ス の ス長は 4 〜 5 - 2 8 〜 3 5 でぁるか ら、 4 0 ¾も あれば十分である。 ただし、 こ こでは、 仮 1 に多 少余裕を見て ス長 4 ¾と したとする。 対応す る ス記憶回路を模式的に表現したのが第 4 Sである < 鞭方向が ト レ リ ス上の状態を、 横方向が ス の段階 ( す ¾わち時間 ） を表現している 。
    [0037] 第 1 図の回路構成に従って、 一 Sに、 2 つの状態 分の状態遷移情報が得 られ、 生き残 り ス記憶回路に 香き込ま れる もの とする。
    [0038] さて、 状態遷移情報の書き 込みと メ モ リ 上の ト レ ー スパ ッ ク を交互に行な う も の とすれば、 ー復号 ス テ ツ プあた の状態遷移情報の書き込みは 3 2 回 （64 2 ) の反復で完了するが、 この間に ト レ ー スバ ッ ク出来る 量は、 3 2 段、 すなわち ス長 6 4 段の半分ま でしか も どる こ とが出来 い。 ゆえに、 更に次の時刻に対す る状態遷移情報の書き込みと ト レ ー スバ ッ クを継続す る 。 この新しい時刻に対する状態遷移情報の書き込み が終了した時点で ト レ ー スパ ッ クは最終段に到達する こ と にな るが、 既にニ復号ス テ ッ プ分に相当する時間 が絰過しているので、 この ト レ ー スバ ッ ク に よ 最終 段に到達した時点で、 2 個の復号デー タ （ すなわち 2 ビ グ ト ） を復号する よ う にしている。
    [0039] こ の 2 ビ ッ ト の 復号法は極 め て簡翠で あ 、 ト レ ー ス バ ッ ク に よ 最 終 的 に た ど り つ い た 時 刻 - V の 状 態 を k-vと し 、 そ の 2 進表現を
    [0040] k~v ) ( こ こ で、 左側ほ ど古 く 、 右側ほ ど新しい。 以下同 じ、 ：） と したと き 復号デ一タは c-v-5と ς- 4 と な る 。 これ らの復号原理を示した も のが第 5 Α図及 び第 5 B 図である。
    [0041] こ こ て、 復号器演箅部の回路構成が同 じで、 ス 長が ^えば 1 2 8 段に延びたとすれば、 4 復号ステ ツ プにわた り、 状態還移情報の書き込みと ト レ ー スパ ッ クを交互に繰 ！？返し、 ト レ ー スバ ッ クが終了した時点 で 4 個の復号データ をま と めて、 出力すればよ い。
    [0042] 次に ト レ ー ス バ グ クの具体的方法を更に詳し く 説 明する。 既に述べた よ う に状態遷移情報を記慷回路へ 香き込む方法には自 由度がある 。 最 も単純な方法は ト レ リ ス上の状態と記憶回路の番地を同一視する もので 列えば前述の ^で言えば、 状態 "000000 "に対する状態 遷移情報は記憶回路の 0 番地へ、 状態 "000001"に対す る状態遷移情報は記億回路の 1 番地へ……、 状態
    [0043] "111111*に対する状態遷移情報は記憶回路の 6 3 番地へ 記億する ものである 。
    [0044] この場合の ト レ ー スパ ッ ク と は、 符号 ト レ リ ス の 単位セ ル構造に従い、
    [0045] 番地 （ ^3 5 ^β ) ( こ こ では左側が古 く 、 右倜が新しい ） のアク セ ス—情報遷移情報 g C 1 ビ ツ ト ） の銃み出 し→次のア ク セ ス番地
    [0046] ( g ^i βι β β ) の決定
    [0047] とい ウ サイ ク ルをま わすこ とに対応する。 これに対し、 符号 ト レ リ ス上の状態と記憶回路の 番地を独立に考え、 一定の変換則の下に状態遷移情報 を香き込むこ と も 出来る。
    [0048] 第 6 図はこの よ う な変換則の一 ^(を示す も ので、 時間軸が 6 種のモー ドの繰 ！？返し と して表現され、 冽 えば着目 時刻がモー ト， 2 にある と き は、 状態 "000ひ 00" に対する状態遷移情報を記憶回路の 0 番地へ、 状態
    [0049] "000001"に対する状賴遷移情報を記慷回路の 3 2 番地 へ、 · "…、 とい う具合に香き 込む ものである。
    [0050] この場合の ト レ ー スパ ッ ク と は、
    [0051] モ ー ド i の番地 （ i ^s )のア ク セ ス → 状態遷移惰報 g(ibit) の统み出し→次のア ク セ ス番 ½ ί βι β βϊ-χ S i+i 6 ) の決定
    [0052] とい う サイ クルをまわすこ とに対応する。
    [0053] 具 刿と して第 6 図にはス タ ー ト がモ ー ド 6 の 8 番地にある と きの ト レ ー スバ ッ クの様子が表現されて いる。
    [0054] 尚、 この判では 1 時刻過去の同 じ番地へパ ッ クす る確率が ½と な っている こ とが特徴である。
    [0055] また ト レ ー スパ ッ ク に よ 最終的に到着した " 番 地 * に対し、 その時刻のモー ドを考慮する こ とに よ ト レ リ ス上の " 状態 " へ変換する こ とが容易に出来る 従って、 こ の よ ！ 5 方法で も ト レ ースパ ッ クを突現す る ことが出来る。 ま た更に復号器演算部の構成の仕方に よ り一度に 複数の状態に対する状態遷移情報が得 られる場'合には. 復号演算の高速化のため、 ト ー タ ル容易は同 じである が、 複数個の （ 分割された ） 記億回路を用意する こと が原則的であ 、 この場合に も、 記憶回路の区別 も含 めて前回の もの と類似の仕方で ト レ ー ス パ ジ クする こ とが可能である。
    [0056] 特に符号 ト レ リ ス上の " 状態 " と "記慷番地 * を 切 雜す手法では、 独立に複数系統の ト レ ー スバ ッ ク を同時に行な う こ とが可能と な る こ とに注意してお く 次に、 この発明の他の実施 ¾について説明する。 この実施 ^ も 生き残 パ ス長の変動、 あるいは復号器 演算部の回路構成にして柔軟に対応でき る ゲ イ タ ビ復 号法、 復号器を提供する も のである 。
    [0057] ま ず、 この実施 ^の ポイ ン ト を ス記憶回略上の ト レ ー スパ ッ ク （ trace back ) に着目 して説明する。
    [0058] 一般性を失 う こ と な く 、 ト レ リ ス線図上の状態数 に対し、 ス長 V を v - 2 Nsと し、 各状態に対する 状艤遷移情報は、 復号器演算部よ 一度に一状態分の みが得られる回路禅成とする。 ス メ モ リ 回路にラ ン ダ ム アク セ ス メ モ リ を使用し、 状態遷移情報の害き込 みと、 一段の ト レ ー スバッ クを交互に実行する従来の 方法では、 全状鳆分に対する状態遷移情報の書き込み を終了した時点て、 ト レ ー スパ ッ クの方は生き残 ！？ ス の中間点ま でしか も どる こ とが出来るい 。
    [0059] ゆえに、 こ の実施判では、 ス長 ¾ 2 分割し、 2 偶のバ ッ ク ト レーサー ( back tracer) ( ト レ ー ス ツ クを実現する手段 ） を用意し、 1 個のパ ッ ク ト レ ーサ 一が生き残 り ス の第 1 段よ 第 Na段ま で ト レ ー スパ ッ クにいる間に、 一方で同時に も う一方のパ ッ ク ト レ ーサ一が第 （ Ns + 1 ) 段よ 第 2 Ns ( = v ：) 段まで ト レ ー スバ ッ クする よ う に し、 （ k + 1 ) 時刻の全状態 に対する状態間遷移情報の誊き込みが終了した時点で 第 2 のバ ッ ク ト レ ー サーが生き残 り ス の最終段 V ま で到達出来る よ う にした も のである。
    [0060] 第 6 図はこの実施列における ト レ ー スパ ッ クの原 理を示した も の で、 各状態に対する状態間遷移情報を パ ス メ モ リ 回路へ害込む一方で、 2 個のバ ッ ク ト レ ー サ一が同時に、 す ¾わち、 第 1 のパ ッ ク ト レ ーサは生 き残 パ ス の第 1 段よ り 第 Ns段へ、 また第 2 のバ ッ ク ト レーサーは第 1 のバ ッ ク ト レーサーが 1 時刻前に ト レ ー スパ ッ クを完了して到達した最終状態の情報を引 き継ぎ、 第 （ N8 + 1 ) 段よ 第 2NB0)段 （ 最終段 ） に 向けて、 ト レ ー スバ ッ ク動作を実行し、 全ての状態に 対する状態遷移情報の書き込みが終了した時点で、 第
    [0061] 2 のバッ ク ト レーサーは生き残 ス の最終段へ到達 し各復号時刻毎に 1 個の割合で復号データを出力する よ う にしている。 次に ト レー スパ ッ クの具 的方法について述べる 第 2 A 図の ト レ リ ス線図か ら も 類推される よ 5 に 一般の符号化率 ½、 拘束長 k のたたみ込み符号に対す る単位セ ル構造 （ 隣接時刻間の状態遷移構造 ） は第 7 図の よ う に表現出来る こ と に注意してお く 、 ゆえに時 刻 k + 1 の状態 Xn + 1 - C u 0 )に対する状觴間遷移情報 が i ( 0. or l )とする と ト レ ー スバ ッ クに よ 戻るべき 時刻 kの状態は （ i U ) と香ける。 同様にして状態 ( i u ) に対する状態間遷移情報が i'とする と、 ト レ ー スパ ッ ク に よ り も どるべき 時刻 （ k 一 1 ) の状態は ( i' i uk-k+3 … uk- ί )と な る。 以下同様の手順に よ り 次々 と 1 時刻前の も どるべき状態が決定し ト レ ー スパ ッ クが実行される。
    [0062] 従ってパ ス メ モ リ 回路を RAM(Random Access Memory) に よ 実現する と し、 更に ト レ リ ス線図上の " 状態 " と メ モ リ の番地と を同一視したとすれば、 H 指定された番地のアク セ ス→ RAMか らの状艤遷移情 報の読み出 し—次にア ク セ スすべ き番地の決定→指 定された番地のァク セ ス *
    [0063] と う サ イ ク ルを繰 返すこ と に よ り ト レ ー スパ ッ ク が行なわれる。 次に この発明の ボイ ン ト と なる、 2 個のパ ッ ク ト レーサー " 情報の引 き継き * であるが、 これは、 第 1 のパ ッ ク ト レーサーが一時刻前に ト レ ー ス バ グ ク に よ り 到達 した最終状態を第 2 のパ ッ ク ト レーサーの初期 状態 と して使用する こ とに よ ] 矛盾 く 実現される。
    [0064] 尚、 第 2 のパ ッ ク ト レーサーに よ ] 、 た ど！？ つ た生き残 ス の最終段の状態 ，
    [0065] … ) に よ り復号データ を決定する こ とは極めて容 募であ 、 この状態を表現 している k 一 1 ) ビ プ ト の う ち最古の ビ ッ ト U Y(_ )+ 2 を復号データ と して出力す ればよい。
    [0066] 次に、 この実施例につ て具体的に説明する。 第
    [0067] 8 図は、 この実施例での復号器の構成例であ り 、 ブラ ン チ メ ト リ ッ ク発生回路 2 0 2 、 ACS 回路 2 0 2 , ス メ ト リ ッ ク記憶回路 2 0 3 、 ノ ス記憶回路 2 0 6 、 制御回路 2 0 4 a , 2 0 4 b 及び 2 個のパ ッ ク ト レ ー サ一 0 5 a ， 2 0 5 b よ ] 構成されている。
    [0068] 以下特に ス記憶回路及び 2 個のバ ッ ク ト レ ーサ —の動作に注 目 して説明する。
    [0069] 第 9 図は、 2 個のパ ッ ク ト レーサーに対応 して、 生き残 ] パ ス記憶回路を 2個の RAMによ ] 実現 したも の で、 第 3 図 と 同様、 縦軸は " 状態 " に、 ま た横轴 は " 時間 * に対応している。 ただし、 時間軸はサイ ク リ ッ クに使用 しているため、 第 3 図の よ う に右端が最 新時刻、 左端が最古時刻 とい う 解釈は一般に出来 い 今、 横軸の （ k + 1 ) 番地が着 目復号ス テ ッ プに対 応 している とする 。 第 9 図中ハ グ チを施 した部分は、 新たに復号器演算部 よ り 得 られた状態遷移情報を メモ リ 回路へ書き込んでいる こ と に対応してる。
    [0070] —方、 このハ ッ チを施 した部分への書き込みが終 了する間に、 2 個のパ ッ ク ト レーサーが各々 の相当領 域を ト レ ー スバ ッ クする様子が表現されている 。 2 個 のパ ッ ク ト レーサーが同時に ト レ ー ス パ ジ ク動作を実 行出来るためには、 これ らのパ ッ ク ト レーサーが常に 異 る RAMをア ク セ ス出来る こ とが必要であるが、 第 9 図の構成では図から明 らかな よ う に、 2 個のパ ッ ク ト レーサーは常に異なる RAMをア ク セ ス しなが ら ト レ — スパ ッ ク を実行して る こ とがわかる 。
    [0071] 更に第 9 図には 2 つのパ ッ ク ト レーサー間の情報 の引 き继ぎの様子が表現されている 。 すなわち、 時刻 ( k + 1 ) において第 1 のパ ッ ク ト レーサーが最終的に 到達 した状態が、 時刻 （ k + 2 ) に いては、 第 2 のパ ッ ク ト レーサーのス タ ー ト 状截と な り 、 一方、 第 2 の パ サ ク ト レーサーが最終的に到達 した状態がその時刻 の復号状態と る ことがわかる 。 ま た復号状態が決定 される と、 時間軸に関 してそのコ ラ ム が不要と な るの で、 次の時刻における状態遷移情報がその不要と つ た コ ラ ム （ すなわち、 （ k + 2 ) 時刻のハ ッ チを施 した 2 部分 ） へ新たに害き込まれる 。 この よ う に して ス メ モ リ 回路を制御する こ とに よ り 長 ス長に対 しても 矛盾 く 復号デー タ を出力する こ とが出来る 。
    [0072] 今ま での説明は第 8 図の構成から も わかる よ う に
    [0073] 5 復号器演算部において、 一度に、 一状態分の状態遷移 情報が得られる もの と したが、 回路構成においては、 一度に複数状態分の状態遷移情報が得 られる場合も あ り う る。
    [0074] 第 1 0 図は、 2 個の ACS 回路 2 0 2 a ， 2 0 2 b o を設ける こ と に よ り、—度に 2つの状態分の状態遷移情報 を得る よ う に したも のである 。 この場合には、 これら 複数個の状態遷移情報を一度に ス メ モ リ 回路 2 0 6 へ書き込むよ う にするが、 この と き 、 例えば、 ト レ リ ス線図上の状態数と ス長がた とえ同 じである と して 1 5 も 、 状態遷移情報の ス メ モ リ 回路 2 0 S への書き込 みと 、 一段の ト レ ー スバ ッ クを交互に操 り返す方法で は、 全ての状態に対する状態遷移情報の甞き込みを終 了 した時点で ト レ ー スバ ッ クは半分 しか完了 し こ と となる。 ゆえに この場合に も 2 個のバ ッ ク ト レ ーサ 0 ： —に よ る ト レ ー スバ ッ クの方法が適用出来る。
    [0075] 尚、 復号器演算部 よ ] 1 度に 2 つの状態分の状態 遷移情報が得 られ、 これらを同時に眷き込むため、 第 8 図 と異 ] 、 ス記憶回路は状態軸に関 して も 2分 割 した回路構成と して る。 ただし ト ー タ ルの容易は 変ィヒ しない。
    [0076] 次に以上の よ う ダ イ タ ビ復号器を LSI と して構 成する場合、 例えば第 8 図の構成か らも わかる よ う に . ブ ラ ン チメ ト リ ッ ク発生回路 2 0 2 、 ACS 回路 2 0 2 . pathメ ト リ ッ ク記憶回路 2 0 3 、 及び制御回路 J 、
    [0077] 2 0 4 a から る回路群と、 制御回路 2 ， 2 0 4 b 、 ノ、 * ヅ ク ト レーサー 2 0 5 a , 2 0 5 b 及び記慷回路 2 0 S か ら る回路群と は機械的に分雜 して考える こ とが出来るので、 これ らの機能を外部 よ り切 り離 して 使用出来るモー ドを持たせる こ とが可能である 。 こ う した機能の分餱は例えば ス長を長 く と り た と き に path記憶回路のみの機能を持たせて他の回路へ付加さ せる こ とが出来るので有効と なる 。
    [0078] 一方 よ く 知 られている よ う に、 グ イ タ ビ復号器に おける ス記憶回路の占めるハ ー ド ウ - ァ上の割合が 非常に大き いので、 該回路を LSI の外部に Sき 、 他の 回路と と も に LSI 化された制御回路に よ この ス記 憶回路を制御する よ う な回路構成 も と う る 。
    [0079] 上述 した実施 に示す よ う に生き残 り パ ス記憶回 路上の ト レ ー スパ - クに関する本発明のダ イ タ ビ復号 器における ス メ モ リ 制御法は、 生き残 り ス長の変 化あるいは復号器演箅部の回路構成に対し柔軟に対応 する こ とが出来、 例えば生き残 ] ス記镓回路を ラ ン ダ ム ア ク セ ス メ モ リ で実現する場合には簡単 ¾番地制 御の変更に よ り 上記の変化に対応する こ とが可能であ る a
    [0080] ま た、 生き残 り ハ° ス記憶回路上の ace back制御 は、 原則的に復号器演算部の制御と独立 しているが、 符号 ト レ リ ス上の " 状態 " とその状態に対する状態遷 移情報を分雜 して扱う こ と に よ り 、 ス メ ト リ ッ ク記 億回路の番地制御に同期させる こ と も 可能である 。
    [0081] 次に例えば Fig. 2 A に示 した よ う 隣接する時刻 間の状態遷移情報である ス選択記号を複数時刻間に 亘つて合成する こ と に よ って、 生き残 り ス記憶回路 上の ト レ ー スパ ッ ク を少ないア ク セ スによ って高速復 号動作とする こ と のでき る実施例について以下に説明 する。
    [0082] 以下に述べる実施例にお て基本と ¾ るパ ス選択 信号の合成法について、 一般性を失 う こ と な く 、 r = - , Κ = 3 の符号を使っ て説明する。
    [0083] Κ - 3 よ ] 、 符号 ト レ リ スは、 2S- 1 =23_ 1 =22 = 4 状態に よ って表現される 。
    [0084] 今、 時刻 V における各拔態に対する ス選択信号 を、 j0O)〜； j30)と甞く こ と にする。 これは、 各状態 に対する生き残 Dパ ス が次の形で終了 している こ とを 示 している o
    [0085] … jQ (v) 00
    [0086] ··· ； O) 01 … j 2(v) 10
    [0087] … j 5 ) 1 1
    [0088] 従って これは、 次の状態遷移と等価である 。
    [0089] ( j 0(v) 0 ) → ( 0 0 )
    [0090] ( j！ (v) 0 ) → ( 0 1 )
    [0091] ( j 2(v) 1 ) → ( 1 0 )
    [0092] ( j 5 ） 1 ) → ( 1 1 )
    [0093] この原理を使って、 2 つの時刻における ス選択 信号を合成する こ とが出来る 。 具体例 と して
    [0094] j 0 (v) = 1 j Q ( v +1 ) = 1
    [0095] j ^v) = 0 j 1 ( v +1 ) = 0
    [0096] 2(v) = 0 j 2 ( v + 1 ) = 1
    [0097] j5(v) = 1 j 5 ( T + 1 ) = 0
    [0098] を考える。
    [0099] t = V の条件よ り
    [0100] ( 1 0 ) → ( 0 0 )
    [0101] ( 0 0 ) → ( 0 1 )
    [0102] ( 0 1 ) → ( 1 0 )
    [0103] ( 1 1 ) → ( 1 1 )
    [0104] 又、 t =v + l の条件よ
    [0105] ( 1 0 ) → ( 0 0 )
    [0106] ( 0 0 ) → ( 0 1 )
    [0107] ( 1 1 ) → ( 1 0 )
    [0108] ( 0 1 ) → ( 1 1 ) 故に、 2つを合成する と、
    [0109] V 4- ( V + 1 )
    [0110] ( 0 1 ) → ( 0 0 )
    [0111] ( 1 0 )→ ( 0 1 )
    [0112] ( 1 1 )→ ( 1 0 )
    [0113] ( 0 0 )→ ( 1 1 )
    [0114] ( ）
    [0115] これは、 時刻 y + i における ト レ リ ス上の状態 " 0 0 "へは、 2時刻前の状態 " 0 1 " よ り遷移する こ と、 同 じ く 、 時刻 （ v + 1 ) における ト レ リ ス上の 状態 w 0 1 * へは .2時刻前の状態 " 1 0 " よ ] 遷移す る こ と等を表わしている 。
    [0116] 実は、 この よ う な合成は、 次の よ う な手厲で容易 に達成する こ とができ る。
    [0117]
    [0118] 0 0
    [0119] 0
    [0120] 0
    [0121] (v) す わち、 セ ル構造 と組み合わせる こ と に よ 、 】·0(ν) = 1 は、 還移 2 → 0 を表わ し ^( = 0 は、 遷移 0 → 1 を表わし j 2(v) = 0 は、 運移 1 → 2 を表わし ； j 5(v) = l は、 遷移 3 → 3 を表わすこ と に る。
    [0122] よ って、 これに従ってス タ ー ト の数字の組を入れ 換えればよい。
    [0123] t - v + 1 にお て も全 く 同様である 。
    [0124] この よ う に して得られた並び （ 0 1 ) は
    [0125] ( 1 0 )
    [0126] ( 1 1 )
    [0127] ( 0 0 )
    [0128] 先に合成した （： ※ ） に一致 している 。
    [0129] なお、 最後に述べた合成の手段は、 パ ス選択信号 の得られる臟序に従って、 前向き に合成する方法るの で、 データ処理の手続上非常に都合がよい。
    [0130] 次に、 今述べた合成の手铙を利用 し、 具体的に得 られる ス選択信号を複数時刻間にわたる状態遍移情 報へ合成 し、 これらの合成データ に基づいた ト レ ー ス パ ッ クが従来の ト レ ー スバ ッ ク と本質的に同一である こ とを確認しておく 。
    [0131] 具体例 と して、 次の よ う に、 ス運択信号が得ら れる こ とを佤定する。 状態 、 T V十 1 v + 2 V + 3 v + 4
    [0132] 00 C
    [0133] 丄 1 0 1 0
    [0134] Λ 0 i - ( 1 ) 0 0 1 0 1 w 10 " ( 2 ) 0 1 1 0 1 w 11 " ( 3 ) 1 0 1 0 0
    [0135] V + 5 V + 6 v + 7
    [0136] 0 0 0
    [0137] 0 1 1
    [0138] 1 0 1
    [0139] 1 0 0
    [0140] —股性を失 う こ と な く 、 今 、 仮 D に 2 ステ ッ プ つ合成する場合を考える 。
    [0141] V V + 1 ス タ ー ト V → ( V +：
    [0142] 1 1 ( 00 ) ( 10 ) ( 01 )
    [0143] 0 0 ( 01 ) ( 00 ) ( 10 )
    [0144] 0 1 ( 10 ) ( 01 ) ( 1 1 )
    [0145] 1 0 ( 1 1 ) ( 11 ) ( 00 )
    [0146] (a) to
    [0147] ΐ 2
    [0148] +寸 A
    [0149]
    [0150] o rH o o o o o
    [0151] Csl
    [0152] これを ト レ ー スパ ッ クする と
    [0153] ( 0 0 )→( 00 )→( 1 1 )→( 0 0 )
    [0154] ( 0 1 )→( 0 0 )→( 1 1 )→( 0 0 )
    [0155] ( 1 0 )→( 0 0 )→( 1 1 )→( 0 0 )
    [0156] ( 1 1 )→( 0 1 )→( 0 0 )→( 0 1 )
    [0157] —方、 も と も との ス選択信号に基づ て従来法 に よ ] ト レ ー スパ ッ クする。
    [0158] V V + 1 V + 2 v + 3
    [0159]
    [0160] L+ 3 v + 4 τ + 5 v+ 6 v + 7
    [0161] 0 0 0 0
    [0162] 0 0
    [0163] 0 0 1
    [0164] 0 0 0 0
    [0165] ゆえに
    [0166] v + 7 τ - 1
    [0167] ( 00 ) ( 0 0 )
    [0168] ( 0 1 ) →· ( 0 0 )
    [0169] ( 1 0 ) ( 00 )
    [0170] ( 1 1 ) →■ ( 0 1 ) これは、 先の合成法の結果と一致する 。 ゆえに、 ス選択信号を複数時間にわたって合成 したデータ に よ っても矛盾な く ト レ ー スバ ッ ク実現する こ とができ
    [0171] O o 以上よ 次の方法を採用する こ とができ る。
    [0172] 手順 1 複数時間区間にわたる合成された状態遷 移情報を生成する 。
    [0173] 手順 2 これらの合成された状態遷移情報に基づ いて ト レ ー ス バ グ クする。
    [0174] 先の例題で示すと V v + 1 v + 2 v + 3
    [0175] 0 1 1 0
    [0176] 0 0 0
    [0177] 2 0 0
    [0178] 3 0 0
    [0179] 合成遷移 合成遷移 v + 4 v + 5 v + 6 v + 7
    [0180] 0 0 0 0
    [0181] 1 0
    [0182] 1 1 0
    [0183] 0 1 0 0
    [0184] I — 1
    [0185] 合成遷移 合成遷移 ( 0 1 ) → ( 0 0 ) ( 1 1 ) → ( 00 )
    [0186] ( 1 0 ) → ( 0 1 ) ( 0 0 ) → ( 0 1 )
    [0187] ( 1 1 ) → d o ) ( 1 0 ) → ( 1 0 ) ( 00 ) → ( 1 1 ) ( 1 0 ) → ( 1 1 )
    [0188] ( 00 ) → ( 00 ) ( 00 ) → ( 0 0 )
    [0189] ( 0 0 ) → ( 0 1 ) ( 01 ) → ( 0 1 )
    [0190] ( 01 ) → ( 1 0 ) ( 0 1 ) → ( 1 0 ) ( 0 1 ) → ( 1 1 ) ( 1 0 ) → ( 1 1 ) ゆえに、 ル ス メ モ リ 回路の構成は次の よ う に ¾ る
    [0191] 時 刻 一
    [0192] V , v +1 v + 2, v + 3 v + 4, v + 5 v-f 6, v-j-7
    [0193] 00
    [0194] 0 1 状 1 0 以下の説明のために、 例えば状態 " 0 0 ' と、 時 刻 y 、 の交点にあるデー タ 0 1 を 0(L) 、 状態
    [0195] " 0 0 ， を時刻 ν + 2 , + 3 との交点のデータ 1 1 を Q( v + 2 ) 等と眷 く こ とにする。
    [0196] 次に、 ス メ モ リ 回路にラ ン ダ ム ア ク セ ス メ モ リ を使ったよ J 詳細 実施例について説明する。 復号手順を具体的にするためには、 復号器演算部 よ り 得 られるパ ス選択信号を も とに、 これらの合成、 合成された遷移情報の ス メ モ リ 回路への害き 込み、 ト レ ー ス パ ッ ク のための ス メ モ リ 回路か らの読み出 し、 そ して、 最終的 ¾復号法等についてタ イ ム チ ヤ一 ト を表現すれば十分である 。
    [0197] 第 1 1 図は、 r = 、 K = 3 の符号に対する一実 施例での ゲ イ タ ビ復号回路の う ち ス メ モ リ 回路の動 作を示すタ イ ム チ ヤ 一 ト の具体例を示す。
    [0198] ①は、 ス選択信号の得 られ方を示 したタ イ ムチ ヤ ー ト であ り 、 Κ = 3 よ 各時刻で 4 つの状態に対す る ス選択信号が順次合成される こ と を示している。
    [0199] ②は、 ①で得られる ス選択信号に対し、 2時刻 間にわたる合成を表現したタ イ ム チ ャ ー ト であ ！？ 、 時 刻 （ v + 1 ) で j i( v + i ) ( 0 ≤ i ≤ 3 ) が得 られる と同 じ状態 i に対する一時刻前のパ ス選択信号 O) と合成する こ と に よ ] 、 合成された状態遷移信号 JLX (y) が得 られる こ と を示 している。
    [0200] ③は、 ②で得 られた合成遷移情報の RAMへの眷き 込みに対する タ イ ム チ ャ ー ト であ ]) 、 4 つの遷移情報 0(ν) 〜 sO) を 2 タ イ ム ス ロ タ ト にわたつ て メ モ リ へ甞き込めば十分である ことを示す。.
    [0201] ④は、 ト レ ー スパ ッ クに相当する タ イ ム チ ャー ト であ 、 こ こでは、 ス メ モ リ 回路へのデータ香き込 みと読み出 しを交互に行 う方法を採用する も の と し ③での書き込み毎に合成された遷移情報を メ モ リ よ り 読み出 し、 ト レ ー スパッ クを実行する こ と を示す。
    [0202] 上述 した よ う に、 パ ス選択信号の合成につ ては ス選択信号の時間的得 られ方に沿って合成でき るた め、 構成上都合がよ く . 又合成する時間長も任意に変 える こ とができ るので、 生き残 り ス長の变勳に応 じ て変更する こ とが可能 と なる 。 又、 この発明の ト レ ー スパ ッ ク法は従来の 1 段毎の ト レ ー スパ ッ ク法の自然 拡張とみる こ とができ るので、 従来技街との整合性 も よい。
    权利要求:
    Claims請 求 の 範 囲
    1. 符号 ト レ リ ス線図の単位セ ル構造に従い、 所定 の時刻 と時刻との間の状態遷移情報を生き残 ス と して、 ス ¾镓回路に記憶させ、 次 で、 この記億さ れた前記状態遷移情報に基づいて ト レ ー スパ ッ クに よ つ て復号デー タ を決定する ゲ イ タ ビ復号器のパ ス メ モ リ 制御法において、 生き残 ス の最終段ま での ト レ ー スパッ クに複数の復号ス テ ッ プを要する と き 、 前記 複数の復号ステ プ数と同 じ数の復号デ一 タを一度に 前記 ス記憶回路から出力する こ とに よ っ て復号デ一 タ を決定する こ とを特徵とする ゲ ィ タ ビ復号器におけ るパ ス メ モ リ 制御法 ·
    2. 前記複数の復号ス テ ッ プ数 と同 じ数の復号デ一 タ を一度に前記 ス記慷回路から 出力する こ と に よ つ て復号デー タを決定するス テ ッ プは、 復号器演算部で 一度に算出された符号 ト レ リ ス上の複数の状態に対す る状態遷移情報を前記 ス記憶回路に同時に害き込む 動作と、 前記 ト レ ー スパ ッ クの 1 段分の ト レ ー ス パ ク ク動作と を交互に実行するステ づ プを有する こ とを特 徵とする請求の範囲第 1 項記載のダ イ タ ビ復号器にお ける ス メ モ リ 制御法 β
    3. 符号 ト レ リ ス線図の単位セ ル構造に従い、 所定 の時刻と時刻との間の状態遷移情報を生き残！） パス と して、 ス記慷回路に ¾慷させ、 次 で、 この記慷さ れた前記状態遷移情報に基づいて、 ト レ ー スバ ッ ク に よ って復号デー タ を決定する グ イ タ ビ復号器に ける ス メ モ リ 制御法におい て 、 生き残 ]) ス の最終段ま での ト レー スパッ ク に複数の復号ス テ ッ プを要する と き 、 複数個の ト レ ー スバ ッ クを行 う手段を設け、 夫々 の ト レ ー スパ ッ ク を行 う手段に よ つ て独立 して ト レ ー スパ ッ クを行 う こ と を特钹とするゲ イ タ ビ復号器に ける ス メ モ リ 制御法 ·
    4. 前記 ト レ ー スパッ クを行 う手段は、 生き残 ]) ノ ス の夫々異 る領域を ト レ ー スパッ ク し、 ある一つの ト レ ー ス パ ッ ク領域の最終段の情報を次の ト レ ー ス パ ッ ク領域の初段の情報 と して設定する こ とを特徵とす る請求の範囲第 3 項記載のダ イ タ ビ復号器に けるパ ス メ モ リ制御法 ·
    5. 符号 ト レ リ ス線図における複数時刻間に亘つて の状態遷移情報を生き残 ] パス と して、 パス記憶回路 に記憶させ、 次いで、 こ の記憶された前記状態遷移情 報に基づいて ト レ ー スパ ッ ク によ って復号デー タを决 定する ゲ イ タ ビ復号器における ス メ モ リ制御法。
    6. 符号 ト レ リ ス線図における複数時刻間に亘つ て の状態遷移情報は、 復号演算部よ ] 得られる各時刻毎 の ス選択信号を、 時間の経緯に従って合成 して得ら れ、 生き残 パ ス の最終段までの ト レ ー スパ ッ クは前 記合成された遷移情報に基づ て複数段ま とめてジ ャ ン プ パ ジ クする こ とに よ って行る う こ と を特徵とする 請求の範囲第 5 項記載の ゲ ィ.タ ビ復号器における ス メ モ リ 制御法。
    10 入力デ' - 9
    io丄 Bm c wet He ¾©络
    ίοζ
    ίθΖ β CS |fl9^ 2
    A Sitハ。； トリック （k + i )
    i030< ί ^(匕ハスメ卜リツ 7 ί
    i03 β ¾¾ίδ ί ^スメトリック 2
    iO冬 ¾小ィ it瘘簟
    io6 « トリック言 ε ιιΐ5^丄
    ίοόβ Λβスメトリック |Εΐ|Β¾2
    Β ハスメトリック Ck)
    C プ メトリック
    D 香 ½刮卸
    Ε
    F 状 叛 2
    書き みデ タ
    Η *欠スティ卜^き
    X ΐεϋΘϋ^リ
    J 書き ^
    Κ し香
    U ^ ¾し =一夕
    H0
    108 ク 1·レー - スメ¾ジ罔 ί^Μ Ι
    20 後号デ夕 N スメモリ阁 ί¾ Μ2
    类似技术:
    公开号 | 公开日 | 专利标题
    US4908827A|1990-03-13|Forward error correction system
    US4853696A|1989-08-01|Code converter for data compression/decompression
    JP4377407B2|2009-12-02|誤り訂正コードインターリーバ
    US4464650A|1984-08-07|Apparatus and method for compressing data signals and restoring the compressed data signals
    EP0066618B1|1986-09-24|Bit serial encoder
    US5935270A|1999-08-10|Method of reordering data
    KR100527891B1|2005-11-15|허프만 디코딩을 수행하는 방법
    US5546409A|1996-08-13|Error correction encoding and decoding system
    Krichevsky2013|Universal compression and retrieval
    US6105159A|2000-08-15|Trellis code with improved error propagation
    EP1397869B1|2006-11-02|Method of decoding a variable-length codeword sequence
    EP0967730B1|2009-10-21|Convolutional decoder with modified metrics
    TWI313107B|2009-08-01|Unified viterbi/turbo decoder for mobile communication systems
    JP2697479B2|1998-01-14|可逆可変長符号化方式
    JP2531479B2|1996-09-04|読取装置
    Jelinek et al.1972|On variable-length-to-block coding
    Gonnet et al.1986|Heaps on heaps
    EP1030457B1|2012-08-08|Methods and system architectures for turbo decoding
    JP4123109B2|2008-07-23|変調装置及び変調方法並びに復調装置及び復調方法
    KR101438072B1|2014-09-03|소거 없는 플래시 메모리의 다중 프로그래밍
    US4606027A|1986-08-12|Error correction apparatus using a Viterbi decoder
    Rader1981|Memory management in a Viterbi decoder
    US7917835B2|2011-03-29|Memory system and method for use in trellis-based decoding
    US5270714A|1993-12-14|Encoding and decoding circuit for run-length-limited coding
    KR20010080157A|2001-08-22|스테이트 머신 기반 인터리버를 가지는 코딩 시스템
    同族专利:
    公开号 | 公开日
    US4905317A|1990-02-27|
    GB8728157D0|1988-01-13|
    GB2198615B|1990-11-28|
    JPS6346819A|1988-02-27|
    GB2198615A|1988-06-15|
    JPS62233933A|1987-10-14|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    1987-10-08| AK| Designated states|Kind code of ref document: A1 Designated state(s): GB US |
    优先权:
    申请号 | 申请日 | 专利标题
    [返回顶部]